package com.yusong.algorithm.link;

/*
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

插入排序的时间复杂度是 O(n^2)
最适合链表的排序算法是归并排序

自顶而下：不断切分，直到为1
自底而上：1变2，2变4，4变8

https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
 */
public class Order148 {

    public static void main(String[] args) {
        int[] data = {9,8,7,6,5,4,3,2,1};
        ListNode node = ListNodeUtil.create(data);

        Order148 demo = new Order148();
        node = demo.sortListBottom(node);
        ListNodeUtil.printNode(node);
    }


    /**
     * 自底向上组合
     * 二分法:由于链表不支持随机访问，快慢指针需要优化，快慢指针变成一个指针先走半程走到慢指针位置，再走半程走到快指针位置
     */
    public ListNode sortListBottom(ListNode head) {
        if(null == head || head.next == null){
            return head;
        }
        int size = 1;
        int length = getLength(head);
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        while (size < length){
            ListNode preNode = dummyHead;
            ListNode cur = dummyHead.next;
            //cur处于需要排序段的头结点
            while (cur != null){
                //针对链表优化的快慢双指针
                ListNode h1 = cur;
                for(int i = 1; i < size && cur.next != null; i++){
                    cur = cur.next;
                }
                ListNode h2 = cur.next;
                ListNode end1 = cur;
                //截断前段
                end1.next = null;
                cur = h2;
                for(int i = 1; i < size && cur != null && cur.next != null; i++){
                    cur = cur.next;
                }

                if(cur != null){
                    ListNode nextH1 = cur.next;
                    cur.next = null;
                    cur = nextH1;
                }

                ListNode newH1 = mergeTwoLists(h1,h2);
                preNode.next = newH1;
                //变更preNode,合并后的段 顺序其实无所谓，只要连接起来即可
                while (preNode.next != null){
                    preNode = preNode.next;
                }
            }

            size = size*2;
        }

        return dummyHead.next;
    }

    /**
     * 递归法
     **/
    public ListNode sortList(ListNode head) {
        //递归终止条件
        if(head == null || head.next == null){
            return head;
        }
        //快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        ListNode head1 = sortList(head);
        head2 = sortList(head2);
        return mergeTwoLists(head1, head2);
    }




    /**
     * 自定顶而下
     * 双指针找中点
     */
    public ListNode sortListTop(ListNode head) {
        if(null == head || head.next == null){
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //双指针找中间节点
        ListNode slow = head;//前半段的结尾 不为空
        ListNode fast = head.next;//后半段的结尾 不为空
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head2 = sortListTop(slow.next);
        //这里要截断链表  不然会死循环
        slow.next = null;
        ListNode head1 = sortListTop(dummyHead.next);
        //合并两个有序的队列
        ListNode newHead = mergeTwoLists(head1, head2);
        return newHead;
    }


    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(null == l1){
            return l2;
        }
        if(null == l2){
            return l1;
        }
        ListNode dummy = new ListNode(Integer.MAX_VALUE);
        ListNode cur = dummy;
        while (l1 != null || l2 != null){
            if(l1 == null){
                cur.next = l2;
                break;
            }
            if(l2 == null){
                cur.next = l1;
                break;
            }
            int val1 = l1.val;
            int val2 = l2.val;
            if(val1 < val2){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        return dummy.next;
    }

    private int getLength(ListNode head){
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }


}


/*
输入：head = [4,2,1,3]
输出：[1,2,3,4]
 */